#include <stdio.h>

int board[8][8];

//打印解决方案
void print_board()
{
    int row;
    int column;
    static int n_solutions;
    
    n_solutions += 1;
    printf("Solution #%d:\n",n_solutions);

    for(row = 0; row < 8; row++){
        for(column = 0; column < 8; column++){
            if(board[row][column])
                printf("Q");
            else
                printf("+");
        }
        putchar('\n');
    }
    putchar('\n');
}

//检测board[row][column]的上半部分的方向上是否有其他皇后
int conflicts(int row, int column)
{
    int i;
    for(i = 1; i < 8; i++){
        if(row - i >= 0 && board[row - i][column])
            return 1;
        if(column - i >= 0 && board[row][column - i])
            return 1;
        if(column + i < 8 && board[row][column + i])
            return 1;

        if(row - i >= 0 && column - i >= 0 && board[row - i][column - i])
            return 1;
        if(row - i >= 0 && column + i < 8 && board[row - i][column + i])
            return 1;
    }
    return 0;
}

//回溯法调用自身
void place_queen(int row)
{
    int column;
    for(column = 0; column < 8; column++){
        board[row][column] = 1;
        if(row == 0 || !conflicts(row,column))
            if(row < 7)
                place_queen(row + 1);
            else
                print_board();
        board[row][column] = 0;
    }
}

int main()
{
    place_queen(0);
    return 0;
}
